package code;

import java.io.ObjectInputStream;
import java.util.Arrays;
import java.util.Scanner;

/**
 * author : yeswater
 * date : 2023/11/29
 * <p>
 * 半径为 k 的子数组平均值
 * <p>
 * 如果在下标 i 前或后不足 k 个元素,那么半径为 k 的子数组平均值是 -1
 * <p>
 * avg[i] 是以子数组平均值
 * <p>
 * 平均值: 去掉结果的小数部分 => 向下取整
 * <p>
 * ans[i-1] =   nums[i−k−1] +   nums[i−k]+⋯+    nums[i+k−1]
 * ans[i]   =   nums[i−k]   +⋯ +nums[i+k−1]+    nums[i+k]
 * <p>
 * ans[i] = ans[i - 1] + nums [i + k] - nums[i - k -1];
 */

public class T2090 {
    public static void main(String[] args) {
        int[] nums = new int[0];
        int k = Integer.MAX_VALUE;
        // System.out.println("please input nums :");
        // Scanner scanner = new Scanner(System.in);
        // if (scanner.hasNextLine()) {
        //     String line = scanner.nextLine();
        //     line = line.replace("[", "");
        //     line = line.replace("]", "");
        //     String[] chars = line.split(",");
        //     nums = new int[chars.length];
        //     for (int i = 0; i < chars.length; i++) {
        //         nums[i] = Integer.parseInt(chars[i]);
        //     }
        //    
        // }
        // System.out.println("please input k :");
        // if (scanner.hasNextLine()) {
        //     k = scanner.nextInt();
        // }
        nums = new int[]{7, 4, 3, 9, 1, 8, 5, 2, 6};
        k = 3;
        // System.out.println(Arrays.toString(Arrays.stream(getAverages(nums, k)).toArray()));
        System.out.println(Arrays.toString(Arrays.stream(getAverages2(nums, k)).toArray()));
        // System.out.println(Arrays.toString(Arrays.stream(getAverages3(nums, k)).toArray()));

    }

    public static int[] getAverages(int[] nums, int k) {
        int length = nums.length;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            if (i < k || length - i <= k) {
                arr[i] = -1; // 元素不足 平均值为 -1
            } else {
                // 计算平均值
                arr[i] = getAvg1(i, k, nums);
            }
        }
        return arr;
    }

    public static int getAvg1(int i, int k, int nums[]) {
        long sum = 0;
        for (int j = i - k; j <= i + k; j++) {
            sum += nums[j];
        }
        return (int) sum / (2 * k + 1);
    }

    public static int getAvg2(int i, int k, int nums[]) {
        int res = nums[i - 1] + nums[i - k] - nums[i + k - 1];
        return res;
    }
    
    public static int[] getAverages2(int[] nums, int k) {
        // 特殊情况 1: k = 0;
        if (k == 0) {
            return nums;
        }
        int n = nums.length;
        // 输出结果
        int[] ans = new int[n];
        // 默认值 全部赋值 -1
        Arrays.fill(ans, -1);
        // 特殊情况 2 : k 值过大
        if (k >= (n+1)/2) {
            return ans;
        }
        
        // 半径内的索引
        int len = k + k + 1;
        long sum = 0;
        // n > i
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }
        // 中心索引
        ans[k] = (int) (sum/len);
        for (int i = k+1; i < n - k; i++) {
            // 根据递推公式: sum[i] = sum[i - 1] + nums [i + k] - nums[i - k -1];
            sum += nums[i+k] - nums[i-k-1];
            ans[i] = (int) (sum/len);
        }
        return ans;
    }

    public static int[] getAverages3(int[] nums, int k) {
        if (k == 0){
            return nums;
        }
        int n = nums.length;
        int [] ans = new int[n];
        if (k >= (n+1)/2){
            Arrays.fill(ans,-1);
            return ans;
        }
        int len = k + k + 1;
        long rangeSum = 0;
        for (int i = 0; i < Math.min(n,len); i++) {
            rangeSum += nums[i];
            ans[i] = -1;
            ans[n-i-1] = -1;
        }
        ans[k] = (int)(rangeSum/len);
        for (int i = k+1; i < n - k; i++) {
            rangeSum += nums[i+k] - nums[i-k-1];
            ans[i] = (int)(rangeSum/len);
        }

        return ans;
    }

}
